package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/'>在链表中插入最大公约数(Insert Greatest Common Divisors in Linked List)</a>
 * <p>给你一个链表的头 head ，每个结点包含一个整数值。</p>
 * <p>在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。</p>
 * <p>请你返回插入之后的链表。</p>
 * <p>两个数的 最大公约数 是可以被两个数字整除的最大正整数。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [18,6,10,3]
 *              18 -> 6 -> 10 -> 3
 *      输出：[18,6,6,2,10,1,3]
 *              18 -> <a color='blue'>6</a> -> 6 -> <a color='blue'>2</a> -> 10 -> <a color='blue'>1</a> -> 3
 *      解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
 *          - 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。
 *          - 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。
 *          - 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。
 *          所有相邻结点之间都插入完毕，返回链表。
 *
 * 示例 2：
 *      输入：head = [7]
 *      输出：[7]
 *      没有相邻结点，所以返回初始链表。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *     <li>链表中结点数目在 [1, 5000] 之间。</li>
 *     <li>1 <= Node.val <= 1000</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/12 13:30
 */
public class LC2807InsertGreatestCommonDivisorsInLinkedList_M {

    static class Solution {
        public ListNode insertGreatestCommonDivisors(ListNode head) {
            ListNode currNode = head;
            while (currNode != null && currNode.next != null) {
                ListNode newNode = new ListNode(getGreatestCommonDivisor(currNode.val, currNode.next.val));
                newNode.next = currNode.next;
                currNode.next = newNode;
                currNode = currNode.next.next;
            }
            return head;
        }

        private int getGreatestCommonDivisor(int num1, int num2) {
            while (num2 > 0) {
                int r = num1 % num2;
                num1 = num2;
                num2 = r;
            }
            return num1;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(18);
        head1.next = new ListNode(6);
        head1.next.next = new ListNode(10);
        head1.next.next.next = new ListNode(3);

        ListNode head2 = new ListNode(7);

        Solution solution = new Solution();
        Printer.printListNode(solution.insertGreatestCommonDivisors(head1));
        Printer.printListNode(solution.insertGreatestCommonDivisors(head2));
    }
}
